package com.zjsru.oneDay202211;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * @Author: CookLee
 * @Date: 2022/11/14 数组的均值分割
 * <p>
 * 我们要将 nums 数组中的每个元素移动到 A 数组 或者 B 数组中，使得 A 数组和 B 数组不为空，并且 average(A) == average(B) 。
 * <p>
 * 如果可以完成则返回true ， 否则返回 false  。
 * <p>
 * 输入: nums = [1,2,3,4,5,6,7,8] 输出: true 解释: 我们可以将数组分割为 [1,4,5,8] 和 [2,3,6,7], 他们的平均值都是4.5。
 */
public class SplitArraySameAverage {
    
    /**
     * cv复制的
     * */
    public boolean splitArraySameAverage(int[] nums) {
        int n = nums.length, m = n / 2, sum = 0;
        for (int x : nums) {
            sum += x;
        }
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int s = 0; s < (1 << m); s++) {
            int tot = 0, cnt = 0;
            for (int i = 0; i < m; i++) {
                if (((s >> i) & 1) == 1) {
                    tot += nums[i];
                    cnt++;
                }
            }
            Set<Integer> set = map.getOrDefault(tot, new HashSet<>());
            set.add(cnt);
            map.put(tot, set);
        }
        for (int s = 0; s < (1 << (n - m)); s++) {
            int tot = 0, cnt = 0;
            for (int i = 0; i < (n - m); i++) {
                if (((s >> i) & 1) == 1) {
                    tot += nums[i + m];
                    cnt++;
                }
            }
            for (int k = Math.max(1, cnt); k < n; k++) {
                if (k * sum % n != 0) {
                    continue;
                }
                int t = k * sum / n;
                if (!map.containsKey(t - tot)) {
                    continue;
                }
                if (!map.get(t - tot).contains(k - cnt)) {
                    continue;
                }
                return true;
            }
        }
        return false;
    }
    
    
    public boolean splitArraySameAverage2(int[] nums) {
        int n = nums.length;
        if (n < 2) {
            return false;
        }
        int sum = 0, mid = n / 2;
        //求出数组总和 并且计为平均数 为后续计算做准备
        for (int num : nums) {
            sum += num;
        }
        //将原数组每个值乘n 相当于总和变为sum * n 所以平均数为sum
        //再将每个数减去平均数 原问题就转变成了在变化后的数组找出一些元素 和为0
        //因为sum(A) / k = sum(总和) / n
        //那我们找到A的和为0时 剩余的部分和也一定为0
        for (int i = 0; i < n; i++) {
            nums[i] = nums[i] * n - sum;
        }
        //用来存储折半查找前半部分的可能出现和
        Set<Integer> set = new HashSet<Integer>();
        //左半部分查找总可能 比如mid为4 一共有2^4 - 1即15中可能即 [1, 15]
        for (int i = 1; i < (1 << mid); i++) {
            int total = 0;
            for (int j = 0; j < mid; j++) {
                //该步用位运算模拟当前位置元素是否参选 比如6 = 0110 即1号与2号为元素选中
                //则此步骤的total = nums[1] + nums[2]
                if ((i & (1 << j)) != 0) {
                    total += nums[j];
                }
            }
            //如果能找到总和为0的组合 此部分平均值为0 映射总sum的平均值为0 即一定能满足
            if (total == 0) {
                return true;
            }
            //否则加入总和集合 为后半部分查找做准备
            if (!set.contains(total)) {
                set.add(total);
            }
        }
        
        //右半部分查找前 先计算一遍总和 用于过滤特殊情况
        int rSum = 0;
        for (int i = mid; i < n; i++) {
            rSum += nums[i];
        }
        //右半部分折半查找 前部分枚举了mid位 后半部分为 n - mid位
        for (int i = 1; i < (1 << (n - mid)); i++) {
            int total = 0;
            //此部分计算与前半部分模拟计算方法一致
            for (int j = mid; j < n; j++) {
                if ((i & (1 << (j - mid))) != 0) {
                    total += nums[j];
                }
            }
            //等于0这部分集合与前半部分判定一致
            //左半部分和包含了当前部分的总和 证明该部分集合加上前半部分集合正好为0 剩余部分总成B集合
            //同时过滤掉特殊情况 即后半部分不能全部选择和前半部分组成A集合 这样B集合就为空了 违反要求AB都不为空的情况
            if (total == 0 || (rSum != total && set.contains(-total))) {
                return true;
            }
        }
        return false;
        
    }
    
    
    public static void main(String[] args) {
        SplitArraySameAverage splitArraySameAverage = new SplitArraySameAverage();
        int[] nums = new int[] {1, 2, 3, 4, 5, 6, 7, 8};
        System.out.println(splitArraySameAverage.splitArraySameAverage(nums));
    }
}
